
#ifndef LRU_K_H
#define LRU_K_H
#include <atomic>
#include <cstdint>
#include <list>
#include <memory>
#include <mutex>
#include <unordered_map>
#include "option/config.h"
namespace boltDB {

class LRUKReplacer {
 public:
  /**
   * @brief a new LRUKReplacer.
   * @param num_frames the maximum number of frames the LRUReplacer will be
   * required to store
   */
  explicit LRUKReplacer(size_t num_frames, size_t k);

  //   DISALLOW_COPY_AND_MOVE(LRUKReplacer);

  /**
   * @brief 销毁 LRUKReplacer.
   */
  ~LRUKReplacer() = default;

  /**
   * @brief Find the frame with largest backward k-distance and evict that
   * frame. Only frames that are marked as 'evictable' are candidates for
   * eviction.
   *
   * A frame with less than k historical references is given +inf as its
   * backward k-distance. If multiple frames have inf backward k-distance, then
   * evict frame with earliest timestamp based on LRU.
   *
   * Successful eviction of a frame should decrement the size of replacer and
   * remove the frame's access history.
   *
   * @param[out] frame_id id of frame that is evicted.
   * @return true if a frame is evicted successfully, false if no frames can be
   * evicted.
   */
  auto Evict(frame_id_t *frame_id) -> bool;

  /**
   *
   * @brief Record the event that the given frame id is accessed at current
   * timestamp. Create a new entry for access history if frame id has not been
   * seen before.
   *
   * If frame id is invalid (ie. larger than replacer_size_), throw an
   * exception. You can also use BUSTUB_ASSERT to abort the process if frame id
   * is invalid.
   *
   * @param frame_id id of frame that received a new access.
   * @param access_type type of access that was received. This parameter is only
   * needed for leaderboard tests.
   */
  void RecordAccess(frame_id_t frame_id);

  /**
   * @brief Toggle whether a frame is evictable or non-evictable. This function
   * also controls replacer's size. Note that size is equal to number of
   * evictable entries.
   *
   * If a frame was previously evictable and is to be set to non-evictable, then
   * size should decrement. If a frame was previously non-evictable and is to be
   * set to evictable, then size should increment.
   *
   * If frame id is invalid, throw an exception or abort the process.
   *
   * For other scenarios, this function should terminate without modifying
   * anything.
   *
   * @param frame_id id of frame whose 'evictable' status will be modified
   * @param set_evictable whether the given frame is evictable or not
   */
  void SetEvictable(frame_id_t frame_id, bool set_evictable);

  /**
   * @brief Remove an evictable frame from replacer, along with its access
   * history. This function should also decrement replacer's size if removal is
   * successful.
   *
   * Note that this is different from evicting a frame, which always remove the
   * frame with largest backward k-distance. This function removes specified
   * frame id, no matter what its backward k-distance is.
   *
   * If Remove is called on a non-evictable frame, throw an exception or abort
   * the process.
   *
   * If specified frame is not found, directly return from this function.
   *
   * @param frame_id id of frame to be removed
   */
  void Remove(frame_id_t frame_id);

  /**
   * TODO(P1): Add implementation
   *
   * @brief Return replacer's size, which tracks the number of evictable frames.
   *
   * @return size_t
   */
  auto Size() -> size_t;

 private:
  class LRUKInfo {
    /** History of last seen K timestamps of this page. Least recent timestamp
     * stored in front. */
   public:
    LRUKInfo(size_t k, frame_id_t fid) : k_(k), fid_(fid) {}
    ~LRUKInfo() = default;
    auto GetKDistance(size_t now) -> int32_t;

   public:
    using ptr = std::unique_ptr<LRUKInfo>;
    size_t last_accuess_time_;
    size_t access_count_;
    size_t k_;
    frame_id_t fid_;
    bool is_evictable_{false};
  };

  auto Cache(LRUKInfo::ptr cache_node) -> std::list<LRUKInfo::ptr>::iterator;

  using LRUKInfo_location = std::list<LRUKInfo::ptr>::iterator;
  auto CacheListModifyLocation(LRUKInfo_location old_location)
      -> std::list<LRUKInfo::ptr>::iterator;
  //  缓存哈希链表
  std::unordered_map<frame_id_t, std::list<LRUKInfo::ptr>::iterator>
      under_k_node_table_;
  std::list<LRUKInfo::ptr> cache_;
  // 访问次数低于k次的链表
  std::unordered_map<frame_id_t, std::list<LRUKInfo::ptr>::iterator>
      cached_node_table_;
  std::list<LRUKInfo::ptr> under_k_node_queue;
  // 其它属性
  std::atomic_uint32_t current_timestamp_{0};
  std::atomic_uint32_t curr_size_{0};
  size_t replacer_size_;
  size_t k_;
  std::mutex latch_;
};
}  // namespace boltDB
#endif  // LRU_K_H
